---
title: "123"
created: 2025-11-28
tags:
  - 算法
---

# 123

## 题目 [123](https://www.lanqiao.cn/problems/1591/learning/)

![[image-b8962659.png]]

## 思路分析

啊？我又看错题了？

不是 蓝桥杯你在干什么

好吧 不是想象中的那么简单 这个数据范围

而且就是暴力构造出来做前缀和 好像也不是那么好构造

应该是要算循环节类似的用规律快速找到是第几组123……

![[image-f7c2e13a.png]]

我以为已经很妙了 结果只能过4个……6分 也还行

其实只差一步之遥了……基本分析到了 少了一个转换 有点可惜 但是能做到这里已经很不错了

数列中的每一个连续的部分可以看作一个小区间。

```text
1 12 123 1234 12345 ...
```

每一个小区间都是一个 $a_1=1$、$d=1$ 的等差数列，且区间的长度也能构成等差数列。

由于 $l, r \le 10^{12}$，即

![[image-fa4bafb0.png]]

所以最多有 1414214 个小区间构成该数列，满足任意 $l, r$ 都能落在里面。

这意味着虽然我们不能直接查询某一位置的前缀和，但可以通过这些小区间来定位和计算某一位置的前缀和。

- 第 $i$ 个区间的元素个数为 $i$。
- 定义 $a[i]$ 表示前 $i$ 个小区间的元素个数（$1\sim n$ 的和）。则有：$a[i]=a[i-1]+i$。
- 定义 $s[i]$ 表示前 $i$ 个小区间的和。则有：$s[i]=s[i-1]+a[i]$。
- 对于数列中任意位置 $i$，一定存在一个最大的 $j$ 满足 $a[j]\le i$，这表示第 $i$ 个数落在第 $j+1$ 区间内。
- 对于数列中任意位置 $i$，当它落在第 $j+1$ 个区间，它是该区间第 $k$ 个数，则它在数列中的前缀和为：$s[j]+a[k]$，其中
  $k=i-a[j]$。

```cpp
#include <iostream>
#define long long long
#define maxn 1414215
using namespace std;
long a[maxn], s[maxn];

long preSum(long i)
{
    int l = 0, r = maxn, mid;
    while (l < r)
    {
        mid = l + r + 1 >> 1;
        if (a[mid] > i) r = mid - 1;
        else l = mid;
    }
    return s[l] + a[i - a[l]];
}

int main()
{
    for (int i = 1; i < maxn; i++)
    {
        a[i] = a[i - 1] + i;
        s[i] = s[i - 1] + a[i];
    }
    int t;
    scanf("%d", &t);
    while (t--)
    {
        long l, r;
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", preSum(r) - preSum(l - 1));
    }
    return 0;
}
```

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=40010;
LL a[N],s[N];
int T;

LL find_group(LL x){
	LL l=1,r=N;
	while(l<r){
		LL mid=(l+r)/2;
		if(a[mid]>=x)
			r=mid;
		else
			l=mid+1;
	}
	return r;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	for(int i=1;i<N;i++){
		a[i]=((1+i)*i)/2;
		s[i]=s[i-1]+a[i];
	}
	cin>>T;
	while(T--){
		LL L,R;cin>>L>>R;

		auto gl=find_group(L);
		LL idxl=gl-(a[gl]-L);
		LL temp=0;
		for(int i=1;i<idxl;i++)		temp+=i;
		LL sl=s[gl-1]+temp;

		auto gr=find_group(R);
		LL idxr=gr-(a[gr]-R);
		temp=0;
		for(int i=1;i<=idxr;i++)	temp+=i;
		LL sr=s[gr-1]+temp;

		cout<<sr-sl<<endl;
	}
	return 0;
 }
```

## 同类题型

## 视频讲解

---
⬅️ [[大写|大写]] 🏠 [[00-冲刺国赛]] ➡️ [[异或变换|异或变换]]